package algorithm;

/** 普利姆算法求最小生成树 */
public class PrimAlgorithm {

  public static void main(String[] args) {
    char[] data = new char[] {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    int verxs = data.length;
    // 邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
    int[][] weight =
        new int[][] {
          {10000, 5, 7, 10000, 10000, 10000, 2},
          {5, 10000, 10000, 9, 10000, 10000, 3},
          {7, 10000, 10000, 10000, 8, 10000, 10000},
          {10000, 9, 10000, 10000, 10000, 4, 10000},
          {10000, 10000, 8, 10000, 10000, 5, 4},
          {10000, 10000, 10000, 4, 5, 10000, 6},
          {2, 3, 10000, 10000, 4, 6, 10000},
        };

    MGraph graph = new MGraph(verxs);
    MinTree minTree = new MinTree();
    minTree.createGraph(graph,verxs,data,weight);

    minTree.prim(graph,1);
  }
}

class MinTree {

  //创建图
  public void createGraph(MGraph graph, int verxs, char[] data, int[][] weight) {
    /*for (int i = 0; i < verxs; i++) {
      graph.verxs=verxs;
      graph.data[i] = data[i];
      System.arraycopy(weight[i], 0, graph.weight[i], 0, verxs);
    }*/
    graph.verxs=verxs;
    graph.data = data;
    graph.weight=weight;
  }


  /**
   * prim算法生成最小生成树
   * v:表示从第几个顶点生成
   */
  public  void prim(MGraph graph,int v){
    //visited[] 标记结点(顶点)是否被访问过
    int[] visited = new int[graph.verxs];
    //把当前这个结点标记为已访问
    visited[v] = 1;
    //h1 和 h2 记录两个顶点的下标
    int h1 = -1;
    int h2 = -1;
    int minWeight = 10000; //将 minWeight 初始成一个大数
    //因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边
    for (int k = 1; k < graph.verxs; k++) {
      for (int i = 0; i < graph.verxs; i++) {
        // i表示已经访问过的结点
        for (int j = 0; j < graph.verxs; j++) {
          //j表示未访问的结点
          if (visited[i]==1&&visited[j]==0&&graph.weight[i][j]<minWeight){
            minWeight=graph.weight[i][j];
            h1=i;
            h2=j;
          }
        }
      }
      //找到一条边是最小
      System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);
      //标记当前结点已经访问
      visited[h2]=1;
      //重置minWeight
      minWeight=10000;
    }


  }
}

class MGraph {
  int verxs; // 结点个数
  int[][] weight; // 邻接矩阵
  char[] data; // 结点数据

  public MGraph(int verxs) {
    verxs = verxs;
    weight = new int[verxs][verxs];
    data = new char[verxs];
  }
}
